Diameter and connectivity of 3-arc graphs

Abstract

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v, u, x, y) of vertices such that both (v, u, x) and (u, x, y) are paths of length two. The 3-arc graph of a given graph G, X (G), is defined to have vertices the arcs of G. Two arcs u v, x y are adjacent in X (G) if and only if (v, u, x, y) is a 3-arc of G. This notion was introduced in recent studies of arc-transitive graphs. In this paper we study diameter and connectivity of 3-arc graphs. In particular, we obtain sharp bounds for the diameter and connectivity of X (G) in terms of the corresponding invariant of G. © 2009 Elsevier B.V. All rights reserved.